#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class Solution
{
 public:
  // 递归
  vector<int> numberofDice(int n)  // 投掷n个骰子，n个骰子的和为n 2n....6n的组合个数/总的组合个数6^n
  {
    vector<int> res;
    // 递归首先明确状态，根据你要求的来：求组合的个数
    // 因此暴力搜索搜一个结果：投掷骰子n次和为sum的组合个数
    // 因为sum是变化的，所以用for循环
    for (int i = n; i <= n * 6; i++) res.push_back(dfs(n, i));  // i为骰子之和sum：n~6n
    return res;
  }

  int dfs(int n, int sum)
  {
    // 递归出口
    if (sum < 0) return 0;
    // DP或者说递归这个状态的结果怎么求，势必要利用递推关系式
    // 可知投掷n次是由投掷n-1次来的，而这样递归到最后n==0
    // 若n==0时，sum==0,此时正解
    if (n == 0) return !sum;

    int res = 0;
    for (int i = 1; i <= 6; i++)
      // 递推关系式
      res += dfs(n - 1, sum - i);
    return res;
  }

  // DP=递归+备忘录 自底而上的迭代
  vector<int> dp_numberofDice(int n)
  {
    vector<vector<int>> f(n + 1, vector<int>(6 * n + 1));  // f(0,0)没有值，便于称呼从1开始
    // 初始条件：表示1个骰子扔出1-6的可能数都为1 d[1][s]=1
    for (int s = 1; s <= 6; s++) f[1][s] = 1;
    // 扔n次(非第一次)
    for (int i = 2; i <= n; i++)  // 第一维
    {
      for (int s = i; s <= 6 * i; s++)  // 第二维
      {
        // 最后一个骰子可以扔1-6点, 若最后一个骰子=5<6,因此都不需要遍历到6
        for (int last = 1; last <= min(last, 6); last++)
        {
          f[i][s] += f[i - 1][s - last];
        }
      }
    }

    double total = pow(6, n);
    vector<double> ans;
    for (int i = n; i <= 6 * n; ++i)
    {
      ans.push_back(f[n][i] * 1.0 / total);
    }
    return ans;
  }
};
